package com.fzy.test.leetcode347;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
        test.differenceOfDistinctValues(new int[][]{{1,2,3},{3,1,5},{3,2,1}});
    }

    public String removeTrailingZeros(String num) {
        char[] str = num.toCharArray();
        int n = str.length;
        for(int j = n-1;j>=0;j--){
            if(str[j] != '0'){
                break;
            }else {
                str[j] = ' ';
            }
        }

        return String.valueOf(str).trim();
    }

    public int[][] differenceOfDistinctValues(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] answer = new int[m][n];

        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                int[] topLeft = getTopLeft(grid,i,j);
                int[] bottom = getBottomRight(grid,i,j);

                Set<Integer> set = new HashSet<>();
                for(int k = 0;k<topLeft.length;k++){
                    set.add(topLeft[k]);
                }
                int diffTopLeft = set.size();

                Set<Integer> setDiffBottom = new HashSet<>();
                for(int k = 0;k<bottom.length;k++){
                    setDiffBottom.add(bottom[k]);
                }
                int diffBottom = setDiffBottom.size();


                answer[i][j] = Math.abs(diffBottom-diffTopLeft);
            }
        }
        return answer;
    }

    private int[] getTopLeft(int[][] grid,int x,int y){
        List<Integer> list = new ArrayList<>();

        for (int i = x-1,j = y-1;i>=0 && j>=0;i--,j--){
            list.add(grid[i][j]);
        }
        int[] topLeft = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            topLeft[i] = list.get(i);
        }
        return topLeft;
    }

    private int[] getBottomRight(int[][] grid,int x,int y){
        List<Integer> list = new ArrayList<>();

        for(int i = x+1,j = y+1;i<grid.length && j<grid[0].length;i++,j++){
            list.add(grid[i][j]);
        }
        int[] bottomRight = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            bottomRight[i] = list.get(i);
        }
        return bottomRight;
    }



    int[][] mat;
    int[][] memo;
    int m, n;

    public int maxIncreasingCells(int[][] mat) {

        this.mat = mat;
        m = mat.length;
        n = mat[0].length;
        memo = new int[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = Math.max(res, dfs(mat,i,j));
            }
        }
        return res;
    }

    private int dfs(int[][] mat,int i, int j) {
        if (memo[i][j] > 0) { // 如果已经计算过，直接返回
            return memo[i][j];
        }
        int res = 1;
        for (int k = 0; k < m; k++) {
            if (k == i) { // 同一行，列数变化
                if (mat[k][j] > mat[i][j]) {
                    res = Math.max(res, dfs(mat,k, j) + 1);
                }
            } else { // 同一列，行数变化
                if (mat[k][j] > mat[i][j]) {
                    res = Math.max(res, dfs(mat,k, j) + 1);
                }
            }
        }
        for (int k = 0; k < n; k++) {
            if (k == j) { // 同一列，行数变化
                if (mat[i][k] > mat[i][j]) {
                    res = Math.max(res, dfs(mat,i, k) + 1);
                }
            } else { // 同一行，列数变化
                if (mat[i][k] > mat[i][j]) {
                    res = Math.max(res, dfs(mat,i, k) + 1);
                }
            }
        }
        memo[i][j] = res;
        return res;
    }


}
